package com.datastructure.test.searchrange;

import java.util.ArrayList;

public class SearchRange {

    public static void main(String[] args) {
        SearchRange searchRange = new SearchRange();
        int[] numArray = {4,7,7,8,8,10};
        ArrayList<Integer> numList = new ArrayList<>(numArray.length);
        for (int i = 0; i < numArray.length; i++) {
            numList.add(numArray[i]);
        }
        ArrayList<Integer> range = searchRange.searchRange(numList, 6);
        System.out.println(range);
    }

    public ArrayList<Integer> searchRange (ArrayList<Integer> nums, int target) {
        // write code here
        if(nums==null){
            return nums;
        }
        ArrayList<Integer> result = new ArrayList<>(2);
        result.add(-1);
        result.add(-1);
        doSearchRange(nums,target,0,nums.size()-1,result);
        return result;
    }

    public void doSearchRange(ArrayList<Integer> nums, int target,int start,int end,ArrayList<Integer> result) {
        if(start>end){
            return;
        }
        int midIndex = (start+end)/2;
        int midValue = nums.get(midIndex);
        if(midValue>target){
            doSearchRange(nums,target,start,midIndex-1,result);
        } else if(midValue<target){
            doSearchRange(nums,target,midIndex+1,end,result);
        } else {
            int temp = midIndex-1;
            while (temp>=0&&nums.get(temp)==target){
                temp--;
            }
            result.set(0,temp+1);
            temp = midIndex+1;
            while (temp<= nums.size()-1&&nums.get(temp)==target){
                temp++;
            }
            result.set(1,temp-1);
        }
    }
}
